Pada 1519, Cortés meninggalkan Cuba dengan 11 buah kapal, 500 anak kapal, dan 15 ekor kuda. Sewaktu kunjungan yang singkat di Yucatán dan Tabasco, beliau bernasib baik kerana berjumpa dengan dua penterjemah, seorang hamba abdi Aztek yang bernama La Malinche, dan seorang lelaki Sepanyol bernama Jeronimo de Aguilar yang fasih dalam bahasa Sepanyol dan dialek Maya setelah menjadi rakyat puak Maya selama tujuh tahun. Cortés mendarat di suatu tempat yang beliau panggil Veracruz ("Salib yang Benar") pada 4 Mac 1519.

Puak pribumi disana, iaitu Totonac dari Cempoala, menghadiahkan Cortés dengan makanan, bulu burung, emas dan wanita. Beliau mendapat tahu bahawa tanah Mexico dimiliki oleh Maharaja Agung dari ibu kota Tenochtitlán. Selang beberapa hari, perwakilan dari Maharaja Mexica/Aztek Moctezuma II tiba dengan membawa lebih banyak hadiah bernilai dengan harapan bahawa emas tersebut dapat memuaskan beliau. Namun, perbuatan ini hanya meningkatkan nafsu Cortés untuk menakluk Mexico. Cortés kemudian diberitahu bahawa beliau disyaki sebagai Quetzalcoatl atau wakilnya, suatu manusia-dewa legenda yang akan merampas kembali ibu kota Tenochtitlán pada tempoh "satu rid" ("satu rid" (bahasa Inggeris: One-Reed) dalam kalendar Aztek adalah bersamaan dengan 52 tahun, yang secara kebetulan jatuh pada tahun 1519). La Malinche kemudiannya menasihati beliau untuk mengambil kesempatan penuh mitos Quetzalcoatl untuk menewaskan Moctezuma.

Cortés memulakan perjalanannya dengan hentian pertama di Tlaxcala, sebuah negeri bebas di Mexico. Pada mulanya, rakyatnya menyerang tentera Cortez tetapi terpaksa akur dengan kecanggihan senjata Sepanyol seperi pedang, kapak, kuda dan senjata api. Cortés kemudian membuat perjanjian dengan mereka bahawa sekiranya mereka memeluk agama Kristian, mereka akan diampun dan beliau akan berusaha untuk menjatuhkan Maharaja Moctezuma, musuh ketat mereka. Tetapi jika mereka enggan bekerjasama, mereka semua akan dibunuh. Akhirnya puak Tlaxcaltecas bersetuju, dan Cortés menyambungkan perjalanannya dengan hampir 2,000 perwira Tlaxcalteca ke arah ibu kota Mexico.

Selepas Cortés tiba di Cholula, bandar kedua terbesar di Empayar ini, La Malinche memberitahu beliau terdapat khabar angin bahawa puak tempatan merancang untuk membunuh askarnya sewaktu mereka sedang tidur. Tanpa banyak soal, beliau mengarahkan tenteranya untuk membunuh kesemua rakyat di Cholula. Tenteranya yang ganas itu kemudiannya membakar bandar tersebut dan membunuh hampir 30,000 penduduk di sana. Selepas itu, Cortés menghantar utusan kepada Moctezuma menceritakan bahawa ketua Cholula menghinakannya dan telah dihukum, tetapi sekiranya Moctezuma menghormati beliau dan terus menghadiahkan emas, Maharaja itu tidak perlu takut dengan kemarahannya.

Apabila penakluk-penakluk dari Sepanyol sampai di bandar Tenochtitlán buat pertama kalinya, mereka takjub dengan kehebatan bandar tersebut. Bagaimanakah orang-orang yang jahil ini boleh hidup dalam kemewahan sebegini? Mereka tiba di pusat Mexica-Aztek pada 8 November 1519. Moctezuma kemudiannya menjemput Cortés ke Tenochtitlán yang terletak di Jalan Tambak Agung menujui "Venice di Barat" yang mungkin merupakan ibu kota terbesar di dalam dunia ketika itu.